{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Paths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #string #backtracking #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #字符串 #回溯 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: binaryTreePaths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的所有路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二叉树的根节点 <code>root</code> ，按 <strong>任意顺序</strong> ，返回所有从根节点到叶子节点的路径。</p>\n",
    "\n",
    "<p><strong>叶子节点</strong> 是指没有子节点的节点。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/12/paths-tree.jpg\" style=\"width: 207px; height: 293px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,null,5]\n",
    "<strong>输出：</strong>[\"1-&gt;2-&gt;5\",\"1-&gt;3\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[\"1\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[1, 100]</code> 内</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-paths](https://leetcode.cn/problems/binary-tree-paths/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-paths](https://leetcode.cn/problems/binary-tree-paths/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,null,5]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getpath(self, root, path, result):\n",
    "        path.append(root.val)\n",
    "        if not root:\n",
    "            return []\n",
    "        if not root.left and not root.right:\n",
    "            spath = '->'.join(map(str, path))\n",
    "            result.append(spath)\n",
    "        if root.left:\n",
    "            self.getpath(root.left, path, result)\n",
    "            path.pop()\n",
    "        if root.right:\n",
    "            self.getpath(root.right, path, result)\n",
    "            path.pop()\n",
    "\n",
    "\n",
    "\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        path = []\n",
    "        result = []\n",
    "        self.getpath(root, path, result)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        res = []\n",
    "        path = []\n",
    "\n",
    "        def backtrack(root):\n",
    "            path.append(str(root.val))\n",
    "            if not root.left and not root.right:\n",
    "                res.append('->'.join(path))\n",
    "                return\n",
    "            if root.left:\n",
    "                backtrack(root.left)\n",
    "                path.pop()\n",
    "            if root.right:\n",
    "                backtrack(root.right)\n",
    "                path.pop()\n",
    "        \n",
    "        backtrack(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        stack,path_st,paths = [root],[str(root.val)],[]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            path = path_st.pop()\n",
    "            if not (cur.left or cur.right):\n",
    "                paths.append(path)\n",
    "            if cur.left:\n",
    "                stack.append(cur.left)\n",
    "                path_st.append(path+'->'+str(cur.left.val))\n",
    "            if cur.right:\n",
    "                stack.append(cur.right)\n",
    "                path_st.append(path+'->'+str(cur.right.val))\n",
    "        return paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        def construct_path(root,path):\n",
    "            if root:\n",
    "                path += str(root.val)\n",
    "                if not root.left and not root.right:\n",
    "                    paths.append(path)\n",
    "                else:\n",
    "                    path += '->'\n",
    "                    construct_path(root.left,path)\n",
    "                    construct_path(root.right,path)  \n",
    "        paths = []\n",
    "        construct_path(root,'')\n",
    "        return paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        res = []\n",
    "        self.getPaths(root,\"\",res)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def getPaths(self, root, path, res):\n",
    "        if not root:\n",
    "            return\n",
    "        # 节点值加入当前路径\n",
    "        path += str(root.val)\n",
    "        # 如果当前节点是叶子节点，将当前路径加入结果集\n",
    "        if root.left == None and root.right == None:\n",
    "            res.append(path)\n",
    "        # 如果当前节点不是叶子节点，继续遍历左子树和右子树。\n",
    "        else:\n",
    "            path += '->'\n",
    "            self.getPaths(root.left, path, res)\n",
    "            self.getPaths(root.right, path, res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        if not root:\n",
    "            return []\n",
    "        stack=[root]\n",
    "        stackPath=[]\n",
    "        res=[]\n",
    "        stackPath.append(str(root.val))\n",
    "        while stack:\n",
    "            node=stack.pop()\n",
    "            path=stackPath.pop()\n",
    "            if node.left==None and node.right==None:\n",
    "                res.append(path)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "                stackPath.append(path+\"->\"+str(node.right.val))\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "                stackPath.append(path+\"->\"+str(node.left.val))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        paths=[]\n",
    "        self.construct_path(root,\"\",paths)\n",
    "        return paths\n",
    "    def construct_path(self,root,path,paths):\n",
    "        if root:\n",
    "            path += str(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                paths.append(path)\n",
    "            else:\n",
    "                path += \"->\"\n",
    "                self.construct_path(root.left,path,paths)\n",
    "                self.construct_path(root.right,path,paths)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def lujing(self, root)->List:\n",
    "        if not root:\n",
    "            return []\n",
    "        if not root.left and not root.right:\n",
    "            return [str(root.val)]\n",
    "        y = []\n",
    "        z = str(root.val)\n",
    "        x = self.lujing(root.left)\n",
    "        for i in x:\n",
    "            y.append(z+'->'+i)\n",
    "        x = self.lujing(root.right)\n",
    "        for i in x:\n",
    "            y.append(z+'->'+i)\n",
    "        return y\n",
    "\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        return self.lujing(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        if not root:\n",
    "            return []\n",
    "        if not root.left and not root.right:\n",
    "            return [str(root.val)]\n",
    "        a = self.binaryTreePaths(root.left)\n",
    "        b = self.binaryTreePaths(root.right)\n",
    "        a.extend(b)\n",
    "        return [str(root.val) +'->'+ x for x in a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pre(self,root,res,path):\n",
    "        if not root:return\n",
    "        path+=str(root.val)\n",
    "        if not root.left and not root.right:\n",
    "            res.append(path)\n",
    "        path+='->'\n",
    "        self.pre(root.left,res,path)\n",
    "        self.pre(root.right,res,path)\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        res=[]\n",
    "        self.pre(root,res,'')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def binaryTreePaths(self, root: TreeNode) -> List[str]:\n",
    "        stack = [root]\n",
    "        path = [str(root.val)]\n",
    "        res = []\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            state = path.pop()\n",
    "            if not node.right and not node.left:\n",
    "                res.append(state)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "                path.append(state + \"->\" + str(node.left.val))\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "                path.append(state + \"->\" + str(node.right.val))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: TreeNode) -> List[str]:\n",
    "        res = []\n",
    "        def dfs(root, path):\n",
    "            if not root:\n",
    "                return\n",
    "            path += str(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                res.append(path)\n",
    "            elif not root.right:\n",
    "                dfs(root.left, path + \"->\")\n",
    "            elif not root.left:\n",
    "                dfs(root.right, path + \"->\")\n",
    "            else:\n",
    "                dfs(root.left, path + \"->\")\n",
    "                dfs(root.right, path + \"->\")\n",
    "        dfs(root, \"\")\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        result=[]\n",
    "        if not root:\n",
    "            return None\n",
    "        return self.my_func(root,'',result)\n",
    "        \n",
    "    def my_func(self,root,pre,result):\n",
    "        '''base case'''\n",
    "        if not root.left and not root.right:\n",
    "            result.append(f'{pre}'+f'{root.val}')\n",
    "            \n",
    "        '''递归开始(头左右)'''\n",
    "        if root.left:\n",
    "            self.my_func(root.left,f'{pre}'+f'{root.val}'+'->',result)\n",
    "        if root.right:\n",
    "            self.my_func(root.right,f'{pre}'+f'{root.val}'+'->',result)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        ans = []\n",
    "        def dfs(node, path):\n",
    "            if node is None:\n",
    "                return \n",
    "            if node.left is None and node.right is None:\n",
    "                ans.append(path)\n",
    "            if node.left:\n",
    "                dfs(node.left, path + '->' + str(node.left.val))\n",
    "            if node.right:\n",
    "                dfs(node.right, path + '->' + str(node.right.val))\n",
    "        dfs(root, str(root.val))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        def backtrace(root,path):\n",
    "            if root is None:\n",
    "                return\n",
    "            path.append(root.val)\n",
    "            if root.left is None and root.right is None:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            \"\"\"处理后续\"\"\"\n",
    "            # 准备后续为列表\n",
    "            choices=[]\n",
    "            if root.left is not None:\n",
    "                choices.append(root.left)\n",
    "            if root.right is not None:\n",
    "                choices.append(root.right)\n",
    "            for choice in choices:\n",
    "                backtrace(choice,path)\n",
    "                path.pop()\n",
    "        res=[]\n",
    "        backtrace(root,[])\n",
    "        return ['->'.join(list(map(str,i))) for i in res]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def getPaths(self, root, path, res):\n",
    "        if not root:\n",
    "            return\n",
    "        # 节点值加入当前路径\n",
    "        path += str(root.val)\n",
    "        # 如果当前节点是叶子节点，将当前路径加入结果集\n",
    "        if root.left == None and root.right == None:\n",
    "            res.append(path)\n",
    "        # 如果当前节点不是叶子节点，继续遍历左子树和右子树。\n",
    "        else:\n",
    "            path += '->'\n",
    "            self.getPaths(root.left, path, res)\n",
    "            self.getPaths(root.right, path, res)\n",
    "\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        \n",
    "        res = []\n",
    "        self.getPaths(root, '', res)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        if root == None:\n",
    "            return []\n",
    "        path = []\n",
    "        result = []\n",
    "        self.traceBack(root, path, result)\n",
    "        return result\n",
    "\n",
    "    def traceBack(self, node, path, result):\n",
    "        # 中\n",
    "        path.append(node.val)\n",
    "\n",
    "        # 终止条件：在叶子节点提前结束\n",
    "        if node.left == None and node.right == None:\n",
    "            sPath = '->'.join(map(str, path))   # 对路径进行转换\n",
    "            result.append(sPath)\n",
    "            return\n",
    "        \n",
    "        # 左\n",
    "        if node.left:\n",
    "            self.traceBack(node.left, path, result)\n",
    "            path.pop()\n",
    "        # 右\n",
    "        if node.right:\n",
    "            self.traceBack(node.right, path, result)\n",
    "            path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: TreeNode) -> List[str]:\n",
    "        return [] if not root else [str(root.val)] if not root.left and not root.right else [str(root.val)+\"->\"+i for i in self.binaryTreePaths(root.left)+self.binaryTreePaths(root.right)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        results = []\n",
    "        path_ww = [str(root.val)]\n",
    "        stack = [root]\n",
    "\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            path = path_ww.pop()\n",
    "\n",
    "            if not cur.left and not cur.right:\n",
    "                results.append(path)\n",
    "            \n",
    "            if cur.right:\n",
    "                stack.append(cur.right)\n",
    "                path_ww.append(path+'->'+str(cur.right.val))\n",
    "            if cur.left:\n",
    "                stack.append(cur.left)\n",
    "                path_ww.append(path+'->'+str(cur.left.val))\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traversal(self, path, res, root):\n",
    "        if not root.left and not root.right:\n",
    "            res.append(\"->\".join(path))\n",
    "            return res\n",
    "        if root.left:\n",
    "            path.append(str(root.left.val))\n",
    "            self.traversal(path, res, root.left)\n",
    "            path.pop()\n",
    "        if root.right:\n",
    "            path.append(str(root.right.val))\n",
    "            self.traversal(path, res, root.right)\n",
    "            path.pop()\n",
    "        \n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        if not root:\n",
    "            return None\n",
    "        path = [str(root.val)]\n",
    "        res = []\n",
    "        self.traversal(path, res, root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        ans = []\n",
    "        def dfs(node, path):\n",
    "            if not node:\n",
    "                return \n",
    "            if not node.left and not node.right:\n",
    "                path += str(node.val)\n",
    "                ans.append(path)\n",
    "                return\n",
    "            else:\n",
    "                path += str(node.val) + \"->\"\n",
    "                dfs(node.left,path)\n",
    "                dfs(node.right,path)\n",
    "        dfs(root,\"\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traversal(self, cur, path, result):\n",
    "        path.append(cur.val)\n",
    "        if not cur.left and not cur.right:\n",
    "            sPath = \"->\".join(map(str, path))\n",
    "            result.append(sPath)\n",
    "        if cur.left:\n",
    "            self.traversal(cur.left, path, result)\n",
    "            path.pop()\n",
    "        if cur.right:\n",
    "            self.traversal(cur.right, path, result)\n",
    "            path.pop()\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        path = []\n",
    "        result = []\n",
    "        self.traversal(root, path, result)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        if not root:\n",
    "            return []\n",
    "        h = [root.val]\n",
    "        s = []\n",
    "        self.tree(root,h,s)\n",
    "        return s\n",
    "    def tree(self,root,h,s):\n",
    "        # h.append(root.val)\n",
    "        if root.left:\n",
    "            h.append(root.left.val)\n",
    "            self.tree(root.left,h,s)\n",
    "            h.pop()\n",
    "        if root.right:\n",
    "            h.append(root.right.val)\n",
    "            self.tree(root.right,h,s)\n",
    "            h.pop()\n",
    "        if not root.right and not root.left:\n",
    "            s.append(\"->\".join(map(str,h)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "\n",
    "        def recur(root, path, res):\n",
    "            path += str(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                res.append(path)\n",
    "            if root.left: recur(root.left, path+'->', res)\n",
    "            if root.right: recur(root.right, path+'->', res)\n",
    "        \n",
    "        res = []\n",
    "        path = ''\n",
    "        if not root: return res\n",
    "        recur(root, path, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traverSal(self,node):\n",
    "        self.path.append(node.val)\n",
    "        if node.left == None and node.right == None:\n",
    "            tmp = ''\n",
    "            for i in range(0,len(self.path)-1):\n",
    "                tmp += str(self.path[i])\n",
    "                tmp += '->'\n",
    "            tmp +=str(self.path[-1])\n",
    "            self.result.append(tmp)\n",
    "            return\n",
    "        if node.left:\n",
    "            self.traverSal(node.left)\n",
    "            self.path.pop()\n",
    "        if node.right:\n",
    "            self.traverSal(node.right)\n",
    "            self.path.pop()\n",
    "\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        self.path = []\n",
    "        self.result = []\n",
    "        if root == None:\n",
    "            return self.result\n",
    "        self.traverSal(root)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        path=[]\n",
    "        res=[]\n",
    "        self.traval(root,path,res)\n",
    "        return res\n",
    "    \n",
    "    def traval(self,root,path,res):\n",
    "        path.append(root.val)\n",
    "        if not root.left and not root.right:\n",
    "            spath='->'.join(str(node) for node in path)\n",
    "            res.append(spath)\n",
    "            return\n",
    "        \n",
    "        if root.left:\n",
    "            self.traval(root.left,path,res)\n",
    "            path.pop()\n",
    "        \n",
    "        if root.right:\n",
    "            self.traval(root.right,path,res)\n",
    "            path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        path=[]\n",
    "        result=[]\n",
    "        if not root:\n",
    "            return result\n",
    "        self.travel(root,path,result)\n",
    "        return result\n",
    "    def travel(self,cur,path,result):\n",
    "        path.append(cur.val)\n",
    "        if not cur.left and not cur.right:\n",
    "            spath='->'.join(map(str,path))\n",
    "            result.append(spath)   #到了叶子节点，形成一条完成的链路\n",
    "        if cur.left:\n",
    "            self.travel(cur.left,path,result)\n",
    "            path.pop()\n",
    "        if cur.right:\n",
    "            self.travel(cur.right,path,result)\n",
    "            path.pop()\n",
    "        \n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        #深度搜索\n",
    "        \"\"\"\n",
    "        stack=[root]\n",
    "        stackPath=[str(root.val)]\n",
    "        res=[]\n",
    "\n",
    "        \n",
    "        while stack:\n",
    "            node=stack.pop()\n",
    "            path=stackPath.pop()\n",
    "            if not node.left and not node.right:\n",
    "                res.append(path)\n",
    "            \n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "                stackPath.append(path + \"->\" + str(node.right.val))\n",
    "         \n",
    "    \n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "                stackPath.append(path + \"->\" + str(node.left.val))\n",
    "        return res\n",
    "        \"\"\"\n",
    "\n",
    "        #递归写法\n",
    "        def dfs(root,path):\n",
    "            if root:\n",
    "                path+=str(root.val)\n",
    "                if not root.left and not root.right:\n",
    "                    paths.append(path)\n",
    "                else:\n",
    "                    path+=\"->\"\n",
    "                    dfs(root.left,path)\n",
    "                    dfs(root.right,path)\n",
    "        paths=[]\n",
    "        dfs(root,\"\")\n",
    "        return paths\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from typing import List, Optional\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        if not root:\n",
    "            return []\n",
    "        result = []\n",
    "        path = []\n",
    "        self.traversal(root, path, result)\n",
    "        return result\n",
    "    \n",
    "\n",
    "    def traversal(self, cur: TreeNode, path: List[int], result: List[str]) -> None:\n",
    "        if not cur:\n",
    "            return\n",
    "        path.append(cur.val)\n",
    "        if not cur.left and not cur.right:\n",
    "            spath = '->'.join(map(str, path))\n",
    "            result.append(spath)\n",
    "            return\n",
    "        if cur.left:\n",
    "            self.traversal(cur.left, path, result)\n",
    "            path.pop()\n",
    "        if cur.right:\n",
    "            self.traversal(cur.right, path, result)\n",
    "            path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        path = []\n",
    "        result = []\n",
    "        if not root:\n",
    "            return result\n",
    "        self.traversal(root, path, result)\n",
    "        return result\n",
    "\n",
    "    def traversal(self, cur, path, result):\n",
    "        path.append(cur.val)\n",
    "        if not cur.left and not cur.right:\n",
    "            sPath = \"->\".join(map(str, path))\n",
    "            result.append(sPath)\n",
    "            return\n",
    "        if cur.left:\n",
    "            self.traversal(cur.left, path, result)\n",
    "            path.pop()\n",
    "        if cur.right:\n",
    "            self.traversal(cur.right, path, result)\n",
    "            path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        self.paths = list()\n",
    "        self.path = list()\n",
    "        self.dfs(root)\n",
    "        return self.paths\n",
    "    \n",
    "    def dfs(self,current):\n",
    "        self.path.append(current.val)\n",
    "        if current.left == None and current.right == None:\n",
    "            spath = \"\"\n",
    "            for i in range(len(self.path) - 1):\n",
    "                spath += (str(self.path[i]) + '->')\n",
    "            spath += str(self.path[-1])\n",
    "            self.paths.append(spath)\n",
    "            return\n",
    "        if current.left:\n",
    "            self.dfs(current.left)\n",
    "            self.path.pop()\n",
    "        if current.right:\n",
    "            self.dfs(current.right)\n",
    "            self.path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        path = []\n",
    "        result = []\n",
    "        self.findpath(root, path, result)\n",
    "        return result\n",
    "\n",
    "    def findpath(self, root, path, result):\n",
    "        path.append(str(root.val))\n",
    "        if not root.left and not root.right:\n",
    "            re_path = \"->\".join(path)\n",
    "            result.append(re_path)\n",
    "\n",
    "            return result\n",
    "        \n",
    "        if root.left:\n",
    "            self.findpath(root.left, path, result)\n",
    "            path.pop()\n",
    "        if root.right:\n",
    "            self.findpath(root.right, path, result)\n",
    "            path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        paths = list()\n",
    "        if root == None:\n",
    "            return paths\n",
    "        \n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "\n",
    "        path_queue = collections.deque()\n",
    "        path_queue.append(str(root.val))\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            path = path_queue.popleft()\n",
    "\n",
    "            if node.left == None and node.right == None:\n",
    "                paths.append(path)\n",
    "            else:\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                    path_queue.append(path + '->' + str(node.left.val))\n",
    "\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                    path_queue.append(path + '->' + str(node.right.val))\n",
    "        return paths\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        # 回溯法\n",
    "        res = []\n",
    "        path = []\n",
    "        self.backtrace(root, path, res)\n",
    "        return res\n",
    "\n",
    "    def backtrace(self, root, path, res):\n",
    "        if not root:\n",
    "            return \n",
    "        if not root.left and not root.right:\n",
    "            path.append(root.val)\n",
    "            res.append('->'.join(str(i) for i in path))\n",
    "            return \n",
    "        path.append(root.val)\n",
    "        if root.left:\n",
    "            self.backtrace(root.left, path, res)\n",
    "            path.pop()\n",
    "        if root.right:\n",
    "            self.backtrace(root.right, path, res)\n",
    "            path.pop()\n",
    "        return \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self._result = []\n",
    "        \n",
    "    def dfs(self, node, path):\n",
    "        path += str(node.val)\n",
    "        if not node.left and not node.right:\n",
    "            self._result.append(path)\n",
    "            return \n",
    "        path += '->'\n",
    "        if node.left:\n",
    "            \n",
    "            self.dfs(node.left, path)\n",
    "\n",
    "\n",
    "        if node.right:\n",
    "            self.dfs(node.right, path)\n",
    "\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        self.dfs(root, '')\n",
    "        return self._result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        \n",
    "        def construct_paths(root, path):\n",
    "            if not root:\n",
    "                return \n",
    "            path += str(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                paths.append(path)\n",
    "        \n",
    "            path += '->'\n",
    "            construct_paths(root.left, path)\n",
    "            construct_paths(root.right, path)\n",
    "        paths = []\n",
    "        construct_paths(root, \"\")\n",
    "        return paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        if not root:\n",
    "            return ans\n",
    "        self.traversal(root, path, ans)\n",
    "        return ans\n",
    "\n",
    "    def traversal(self, cur, path, ans):\n",
    "        path.append(cur.val)\n",
    "        if cur.left:\n",
    "            self.traversal(cur.left, path, ans)\n",
    "            path.pop()\n",
    "        if cur.right:\n",
    "            self.traversal(cur.right, path, ans)\n",
    "            path.pop()\n",
    "        if not cur.left and not cur.right:\n",
    "            sPath = \"->\".join(map(str, path))\n",
    "            ans.append(sPath)\n",
    "            return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        ans = []\n",
    "        def dfs(node, s):\n",
    "            if not node:\n",
    "                return\n",
    "            if s:\n",
    "                s = f'{s}->{node.val}'\n",
    "            else:\n",
    "                s = str(node.val)\n",
    "            if not node.left and not node.right:\n",
    "                ans.append(s)\n",
    "                return\n",
    "            dfs(node.left, s)\n",
    "            dfs(node.right, s)\n",
    "        dfs(root, '')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        if not root:return []\n",
    "        queue = [(root,str(root.val))]#最后返回的是字符串路径\n",
    "        res = []\n",
    "        while queue:\n",
    "            node,num = queue.pop(0)\n",
    "            if not node.left and not node.right:\n",
    "                res.append(num)\n",
    "            if node.left:\n",
    "                queue.append((node.left,num + \"->\" + str(node.left.val)))\n",
    "            if node.right:\n",
    "                queue.append((node.right,num + \"->\" + str(node.right.val)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        ans, stack = [], [root]\n",
    "        ar = [str(root.val)]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            val = ar.pop()\n",
    "            if not (node.left or node.right):\n",
    "                ans.append(val)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "                ar.append(val + '->' + str(node.right.val))\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "                ar.append(val + '->' + str(node.left.val))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.record = []\n",
    "\n",
    "    def preorderTraverse(self, node: Optional[TreeNode], path: List):\n",
    "        if node is None:\n",
    "            return\n",
    "        path.append(str(node.val))\n",
    "        if node.left is None and node.right is None:\n",
    "            self.record.append('->'.join(path))\n",
    "        if node.left is not None:\n",
    "            self.preorderTraverse(node.left, path)\n",
    "        if node.right is not None:\n",
    "            self.preorderTraverse(node.right, path)\n",
    "        path.pop()\n",
    "        return\n",
    "\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        self.preorderTraverse(root,list())\n",
    "        return self.record\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        cur = []\n",
    "        result = []\n",
    "        if root is None:\n",
    "            return []\n",
    "        self.recu(root, cur, result)\n",
    "        return result\n",
    "    \n",
    "\n",
    "    def recu(self, root, cur, result):\n",
    "        cur.append(root.val)\n",
    "        if root.left is None and root.right is None:\n",
    "            result.append(\"->\".join(map(str, cur)))\n",
    "            return\n",
    "        if root.left:\n",
    "            self.recu(root.left, cur, result)\n",
    "            cur.pop()\n",
    "        if root.right:\n",
    "            self.recu(root.right, cur, result)\n",
    "            cur.pop()\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        paths = []\n",
    "        def pre_order(root, path):\n",
    "            if not root: return \n",
    "\n",
    "            path += str(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                paths.append(path)\n",
    "            else:\n",
    "                path += '->'\n",
    "                pre_order(root.left, path)\n",
    "                pre_order(root.right, path)\n",
    "        \n",
    "        pre_order(root, path='')\n",
    "        return paths "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        ans=[]\n",
    "        def dfs(node,path):\n",
    "            if not node:\n",
    "                return \n",
    "            if not node.left and not node.right:\n",
    "                path+=str(node.val)\n",
    "                ans.append(path)\n",
    "                return \n",
    "            else:\n",
    "                path+=str(node.val)+\"->\"\n",
    "                dfs(node.left,path)\n",
    "                dfs(node.right,path)\n",
    "        dfs(root,\"\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        res = []\n",
    "        def dfs(node, path):\n",
    "            if not node:\n",
    "                return None\n",
    "            path += str(node.val)\n",
    "            if not node.left and not node.right:\n",
    "                res.append(path)\n",
    "            dfs(node.left, path + '->')\n",
    "            dfs(node.right, path + '->')\n",
    "        \n",
    "        dfs(root, '')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.record = []\n",
    "\n",
    "    def preorderTraverse(self, node: Optional[TreeNode], path: List):\n",
    "        if node is None:\n",
    "            return\n",
    "        path.append(str(node.val))\n",
    "        if node.left is None and node.right is None:\n",
    "            self.record.append('->'.join(path))\n",
    "        if node.left is not None:\n",
    "            self.preorderTraverse(node.left, path)\n",
    "            # 一定要记住一个递归对应一个回溯，python中的List是浅拷贝\n",
    "            path.pop()\n",
    "        if node.right is not None:\n",
    "            self.preorderTraverse(node.right, path)\n",
    "            path.pop()\n",
    "        return\n",
    "\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        self.preorderTraverse(root,list())\n",
    "        return self.record\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        res = []\n",
    "        if root:\n",
    "            if root.left:\n",
    "                t1 = self.binaryTreePaths(root.left)\n",
    "                for i in t1:\n",
    "                    i = str(root.val)+\"->\"+i\n",
    "                    res.append(i)\n",
    "            if root.right:\n",
    "                t1 = self.binaryTreePaths(root.right)\n",
    "                for i in t1:\n",
    "                    i = str(root.val)+\"->\"+i\n",
    "                    res.append(i)\n",
    "            if root.left==None and root.right == None:\n",
    "                return [str(root.val)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        result = list()\n",
    "        if not root:\n",
    "            return result\n",
    "        NodeStack = list()\n",
    "        p = root\n",
    "        pre = None\n",
    "        while len(NodeStack)>0 or p:\n",
    "            if p:\n",
    "                NodeStack.append(p)\n",
    "                p = p.left\n",
    "            else:\n",
    "                p = NodeStack[-1]\n",
    "                if p.right and p.right != pre:\n",
    "                    p = p.right\n",
    "                else:\n",
    "                    p = NodeStack[-1]\n",
    "                    if not p.left and not p.right:\n",
    "                        path = str()\n",
    "                        for node in NodeStack:\n",
    "                            path += str(node.val) + \"->\"\n",
    "                        path = path[:-2]\n",
    "                        result.append(path)\n",
    "                    NodeStack.pop()\n",
    "                    pre = p\n",
    "                    p = None\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        res = []\n",
    "        path = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            #说明遍历到叶子节点了\n",
    "            if not root.left and not root.right:\n",
    "                path.append(str(root.val))\n",
    "                if len(path) > 1:\n",
    "                    tmp = '->'.join(path)\n",
    "                    res.append(tmp)\n",
    "                else:\n",
    "                    res.append(str(root.val))\n",
    "                path.pop()\n",
    "                return\n",
    "            path.append(str(root.val))\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "            path.pop()\n",
    "        dfs(root)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        temp = []\n",
    "        res = []\n",
    "        if root:\n",
    "            temp = self.binaryTreePaths(root.left) + self.binaryTreePaths(root.right)\n",
    "            for i in temp:\n",
    "                res.append(str(root.val) + \"->\" + str(i))\n",
    "            if not res:\n",
    "                res = [str(root.val)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        ans = []\n",
    "        def dfs(root, path):\n",
    "            nonlocal ans\n",
    "            if root.left or root.right:\n",
    "                path.append(str(root.val))\n",
    "                if root.left:\n",
    "                    dfs(root.left, path)\n",
    "                if root.right:\n",
    "                    dfs(root.right, path)\n",
    "                path.pop()\n",
    "                \n",
    "            else:\n",
    "                path.append(str(root.val))\n",
    "                ans.append(\"->\".join(path))\n",
    "                path.pop()\n",
    "        if root:\n",
    "            dfs(root, [])\n",
    "            return ans\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        res = []\n",
    "        if root:\n",
    "            for i in self.binaryTreePaths(root.left) + self.binaryTreePaths(root.right):\n",
    "                res.append(str(root.val) + \"->\" + str(i))\n",
    "            if not res:\n",
    "                res = [str(root.val)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: TreeNode) -> List[str]:\n",
    "        return [] if not root else [str(root.val)] if not root.left and not root.right else [str(root.val)+\"->\"+i for i in self.binaryTreePaths(root.left)+self.binaryTreePaths(root.right)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        result = []\n",
    "        if not root:\n",
    "            return []\n",
    "        node_queue = [root]\n",
    "        path_queue = [str(root.val)]\n",
    "        while node_queue:\n",
    "            node = node_queue.pop(0)\n",
    "            path = path_queue.pop(0)\n",
    "            if not node.left and not node.right:\n",
    "                result.append(path)\n",
    "            else:\n",
    "                if node.left:\n",
    "                    node_queue.append(node.left)\n",
    "                    path_queue.append(path + '->' + str(node.left.val))\n",
    "                if node.right:\n",
    "                    node_queue.append(node.right)\n",
    "                    path_queue.append(path + '->' + str(node.right.val))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        result = []\n",
    "        path = []\n",
    "        if not root:\n",
    "            return result\n",
    "        self.traversal(root, path, result)\n",
    "        return result\n",
    "\n",
    "    def traversal(self, cur, path, result):\n",
    "        path.append(cur.val)\n",
    "        if not cur.left and not cur.right:\n",
    "            stringPath = \"->\".join(map(str,path))\n",
    "            return result.append(stringPath)\n",
    "        if cur.left: \n",
    "            self.traversal(cur.left, path, result)\n",
    "            path.pop()\n",
    "        if cur.right: \n",
    "            self.traversal(cur.right, path, result)\n",
    "            path.pop()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        res = []\n",
    "        def dfs(root,path):\n",
    "            if root is None:\n",
    "                return\n",
    "            \n",
    "            if root.left is None and root.right is None:\n",
    "                path+=str(root.val)\n",
    "                res.append(path)\n",
    "                return \n",
    "            else:\n",
    "                path+=str(root.val)+'->'\n",
    "                dfs(root.left,path)\n",
    "                dfs(root.right,path)\n",
    "        dfs(root,'')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        path = []\n",
    "        paths = []\n",
    "        self.helper(root, path, paths)\n",
    "        return paths\n",
    "\n",
    "    def helper(self, node, path, paths):\n",
    "        if not node.left and not node.right:\n",
    "            path.append(node.val)\n",
    "            paths.append('->'.join(map(str,path)))\n",
    "        elif node.left and not node.right:\n",
    "            path.append(node.val)\n",
    "            self.helper(node.left, path, paths)\n",
    "        elif node.right and not node.left:\n",
    "            path.append(node.val)\n",
    "            self.helper(node.right, path, paths)\n",
    "        else:\n",
    "            path.append(node.val)\n",
    "            self.helper(node.left, path, paths)\n",
    "            self.helper(node.right, path, paths)\n",
    "        path.pop()    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        \n",
    "        def construct_paths(root, path):\n",
    "            if not root:\n",
    "                return \n",
    "            path += str(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                paths.append(path)\n",
    "            else:\n",
    "                path += '->'\n",
    "                construct_paths(root.left, path)\n",
    "                construct_paths(root.right, path)\n",
    "        paths = []\n",
    "        construct_paths(root, \"\")\n",
    "        return paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        # 回溯\n",
    "        if not root:\n",
    "            return [\"\"]\n",
    "        if not root.left and not root.right:\n",
    "            return [str(root.val)]\n",
    "\n",
    "        res = []\n",
    "        path = []\n",
    "        def dfs(node):\n",
    "            path.append(str(node.val))\n",
    "            if not node.left and not node.right:\n",
    "                res.append(\"->\".join(path))\n",
    "            if node.left:\n",
    "                dfs(node.left)\n",
    "            if node.right:\n",
    "                dfs(node.right)\n",
    "            path.pop()\n",
    "        dfs(root)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        result = []\n",
    "        path = ''\n",
    "        self.travel(root, path, result)\n",
    "        return result\n",
    "\n",
    "    def travel(self, cur, path,result):\n",
    "        if cur:\n",
    "            path += str(cur.val)\n",
    "        # 递归结束处理逻辑\n",
    "        if not cur.left and not cur.right:\n",
    "            result.append(path)\n",
    "            return \n",
    "        if cur.left:\n",
    "            self.travel(cur.left, path+'->', result)\n",
    "        if cur.right:\n",
    "            self.travel(cur.right, path+'->', result)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        result = []\n",
    "        path = []\n",
    "\n",
    "        self.traversal(root, path, result)\n",
    "        return result\n",
    "\n",
    "    def traversal(self, cur, path, result):\n",
    "        path.append(cur.val)  # 中\n",
    "        if not cur.left and not cur.right:\n",
    "            sPath = '->'.join(map(str, path))\n",
    "            result.append(sPath)\n",
    "            return\n",
    "        \n",
    "        if cur.left:\n",
    "            self.traversal(cur.left, path, result)\n",
    "            path.pop()\n",
    "        \n",
    "        if cur.right:\n",
    "            self.traversal(cur.right, path, result)\n",
    "            path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        res = []\n",
    "        if root == None:\n",
    "            return res\n",
    "        self.dfs(root, [], res)\n",
    "        return res\n",
    "    def dfs(self, cur, path, res):\n",
    "        if cur == None:\n",
    "            return\n",
    "        path.append(cur.val)\n",
    "        if not cur.left and not cur.right:\n",
    "            res.append('->'.join(map(str,path)))\n",
    "        if cur.left:\n",
    "            self.dfs(cur.left, path[:], res)\n",
    "        if cur.right:\n",
    "            self.dfs(cur.right, path[:],res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        st=[root]\n",
    "        p_st=[str(root.val)]\n",
    "        res=[]\n",
    "        while st:\n",
    "            node=st.pop()\n",
    "            path=p_st.pop()\n",
    "            if not (node.left or node.right):\n",
    "                res.append(path)\n",
    "            if node.right:\n",
    "                st.append(node.right)\n",
    "                p_st.append(path+'->'+str(node.right.val))\n",
    "            if node.left:\n",
    "                st.append(node.left)\n",
    "                p_st.append(path+'->'+str(node.left.val))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        #DFS\n",
    "        res=[]\n",
    "        def dfs(root,path):\n",
    "            if root:\n",
    "                path+=str(root.val)\n",
    "                if not root.left and not root.right:\n",
    "                    res.append(path)\n",
    "                else:\n",
    "                    path+='->'\n",
    "                    dfs(root.left,path)\n",
    "                    dfs(root.right,path)\n",
    "        dfs(root,'')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        ans = []\n",
    "        def f(root, ar):\n",
    "            if not root:\n",
    "                return\n",
    "            ar = ar + [str(root.val)]\n",
    "            if not root.left and not root.right:\n",
    "                ans.append(ar[:])\n",
    "                return\n",
    "            f(root.left, ar)\n",
    "            f(root.right, ar)\n",
    "        f(root, [])\n",
    "        return ['->'.join(i) for i in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        res = []\n",
    "        path = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            #说明遍历到叶子节点了\n",
    "            if not root.left and not root.right:\n",
    "                path.append(str(root.val))\n",
    "                if len(path) > 1:\n",
    "                    tmp = '->'.join(path)\n",
    "                    res.append(tmp)\n",
    "                else:\n",
    "                    res.append(str(root.val))\n",
    "                path.pop()\n",
    "                return\n",
    "            path.append(str(root.val))\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "            path.pop()\n",
    "        dfs(root)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        ans = []\n",
    "        def f(root, ar):\n",
    "            if not root:\n",
    "                return\n",
    "            ar.append(str(root.val))\n",
    "            if not root.left and not root.right:\n",
    "                ans.append('->'.join(ar))\n",
    "                return\n",
    "            if root.left:\n",
    "                f(root.left, ar)\n",
    "                ar.pop()\n",
    "            if root.right:\n",
    "                f(root.right, ar)\n",
    "                ar.pop()\n",
    "        f(root, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "\n",
    "        result = []\n",
    "        tmp = []\n",
    "\n",
    "        def helper(node):\n",
    "            tmp.append(str(node.val))\n",
    "            if not node.left and not node.right:\n",
    "                tmp_result = tmp[:]\n",
    "                result.append('->'.join(tmp_result))\n",
    "                return\n",
    "\n",
    "            if node.left:\n",
    "                helper(node.left)\n",
    "                tmp.pop()\n",
    "\n",
    "            if node.right:\n",
    "                helper(node.right)\n",
    "                tmp.pop()\n",
    "\n",
    "        helper(root)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        self.getPaths(root,'',res)\n",
    "\n",
    "        return res\n",
    "\n",
    "    def getPaths(self,root,path,res):\n",
    "        if not root:\n",
    "            return \n",
    "        # 节点值加入当前路径\n",
    "        path += str(root.val)\n",
    "        # 如果当前节点是叶子节点，将当前路径加入结果集\n",
    "        if not root.left and not root.right:\n",
    "            res.append(path)\n",
    "        else:\n",
    "            path += \"->\"\n",
    "            self.getPaths(root.left,path,res)\n",
    "            self.getPaths(root.right,path,res)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        ans = []\n",
    "        def f(root, ar):\n",
    "            ar.append(str(root.val))\n",
    "            if not root.left and not root.right:\n",
    "                ans.append('->'.join(ar))\n",
    "                return\n",
    "            if root.left:\n",
    "                f(root.left, ar)\n",
    "                ar.pop()\n",
    "            if root.right:\n",
    "                f(root.right, ar)\n",
    "                ar.pop()\n",
    "        f(root, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPath(self, cur: Optional[TreeNode], path: List[int], result: List[str]) -> None:\n",
    "        path.append(cur.val)\n",
    "        if (not cur.left) and (not cur.right):\n",
    "            s = '->'.join(map(str, path))\n",
    "            result.append(s)\n",
    "            return\n",
    "        if cur.left:\n",
    "            self.getPath(cur.left, path, result)\n",
    "            path.pop()\n",
    "        if cur.right:\n",
    "            self.getPath(cur.right, path, result)\n",
    "            path.pop()\n",
    "\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        path = []\n",
    "        result = []\n",
    "        if not root:\n",
    "            return result\n",
    "        self.getPath(root, path, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        res = []\n",
    "        stack = [root]\n",
    "        path_st = [str(root.val)]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            path = path_st.pop()\n",
    "            if not node.left and not node.right:\n",
    "                res.append(path)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "                path_st.append(path + \"->\" + str(node.left.val))\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "                path_st.append(path + \"->\" + str(node.right.val))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\r\n",
    "        self.res = []\r\n",
    "\r\n",
    "        def traverse(root, path):\r\n",
    "            if not root.left and not root.right:\r\n",
    "                self.res.append(path)\r\n",
    "                return\r\n",
    "            if root.left:\r\n",
    "                traverse(root.left, path + \"->\" + str(root.left.val))\r\n",
    "            if root.right:\r\n",
    "                traverse(root.right, path + \"->\" + str(root.right.val))\r\n",
    "        \r\n",
    "        traverse(root, str(root.val))\r\n",
    "        return self.res\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        ans = []\n",
    "        def dfs(root, path):\n",
    "            nonlocal ans\n",
    "            path.append(str(root.val))\n",
    "\n",
    "            if root.left or root.right:\n",
    "                if root.left:\n",
    "                    dfs(root.left, path)\n",
    "                if root.right:\n",
    "                    dfs(root.right, path)\n",
    "            else:\n",
    "                ans.append(\"->\".join(path))\n",
    "            path.pop()\n",
    "        if root:\n",
    "            dfs(root, [])\n",
    "            return ans\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:\n",
    "        def fun(root: Optional[TreeNode],str1) -> str:\n",
    "            if root:\n",
    "                if not root.left and not root.right:\n",
    "                    str1=str1+str(root.val)\n",
    "                    list.append(str1)\n",
    "                else:\n",
    "                    str1=str1+str(root.val)+'->'\n",
    "                    fun(root.left,str1)\n",
    "                    fun(root.right,str1)   \n",
    "        list=[]            \n",
    "        fun(root,'')\n",
    "        return list\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
